The generation of color documents can be thought of as a two step process: first, the generation of the image by means of scanning an original document with a color image input terminal or scanner or, alternatively, creating a color image on a work station operated in accordance with a color image creation program; and secondly, printing of that image with a color printer in accordance with the colors defined by the scanner or computer generated image. Scanners commonly operate with colors defined in a color space of tristimulus values, i.e., RGB (red-green-blue). Commonly, these values are a linear transformation of the standard XYZ coordinates of CIE color space, or a correct transform of those values. In the case of computer generated images, colors defined by the user at the user interface of his workstation are immediately converted into color space values and directed out of the system as defined in the document colors.
Printers have an output which can be defined as existing in a color space called CMYK (cyan-magenta-yellow-key or black) which is uniquely defined for the printer by its capabilities and colorants. Printers operate by the addition of multiple layers of ink or colorant in layers to a page. The response of the printer tends to be relatively non-linear. Thus, while a printer system receives information in a first color space, it must convert that information to print in a second color space.
The desirability of operating in a tristimulus color space with subsequent conversion to a printer colorant color space is well known, such as shown by U.S. Pat. No. 4,500,919 to Schreiber and U.S. Pat. No. 2,790,844 to Neugebauer, and U.S. Pat. No. 4,275,413 to Sakamoto. There are many methods of conversion between color spaces, all of which begin with the measurement of printer response to certain input values. Commonly, a printer is driven with a set of color input values, the values are printed in normal operation of the printer, and measurements are made of those colors to determine what the actual color printed was in response to the color specification. As previously noted, most printers have non-linear response characteristics.
In U.S. Pat. No. 4,500,919 to Schreiber, and U.S. Pat. No. 4,275,413 to Sakamoto, the information derived was placed into look-up tables, stored in a memory, perhaps ROM memory or RAM memory where the look-up table relates input color space to output color space. The look-up table is commonly a three dimensional table since color space is three dimensional. In RGB space, at a scanner or computer, space can be defined as three dimensional with black at the origin of a three dimensional coordinate system 0, 0, 0 and white at the maximum of a three dimensional coordinate system which an 8-bit system, would be located at 255, 255, 255. Each of the three axes radiating from the origin point therefore respectively define red, green, and blue and points therebetween in the volume of the cube defining colors resulting from the combinations of the additive primary colors. A similar construct can be made for the printer, with axes representing cyan, magenta, and yellow. Black is usually a separate toner which is added separately. In the 8-bit system suggested, there will be, however, over 16 million possible colors (256.sup.3). There are clearly too many values for a 1:1 mapping of RGB to CMYK. Accordingly, as proposed in U.S. Pat. No. 4,275,413 to Sakamoto, only a relatively small number of samples are made at the printer, perhaps on the order of 1000-4000. Therefore, the look-up tables (LUT's) consist of a set of values which could be said to be the intersections for corners of a set of rectangular parallelepipeds mounted on top of one another. Colors falling within each rectangular volume can be interpolated from the measured values, through many methods including tri-linear interpolation, tetrahedral interpolation, polynomial interpolation, linear interpolation, and any other interpolation method depending on the accuracy of the desired result.
The interpolation methods described all require information about the grids, and particularly, require information about the distance between adjacent points in space on the grid. The input color space grid has nodes spaced at regular intervals, and accordingly the distance values are derived by simple monotonic functions. The output color space grid is empirically measured and accordingly the nodes are at irregular intervals, which are often not describable by simple functions. In the example of FIG. 1, the regular array of data values in the input color space LUT are indicated by X's, and the point marked with an O is to be derived by interpolation therefrom (as will become apparent, this is a simplified two dimensional example). The LUT holds the value of the function H(x,y) for the points (x[i], y[j]) where x[i]and y[j]are some set of discrete values referred to as the grid points, node points, or lattice points and i runs from 0 to M-1 and j runs from 0 to N-1 (thus giving an M.times.N LUT size). In an example illustrated in FIG. 2, three dimensional tetrahedral interpolation is reduced to two dimensions or triangular interpolation and the value for the desired point is given by: EQU H(x,y)=H[i][j]+.DELTA.x.(H[i+1][j]-H[i][j])+.DELTA.y.(H[i+1][j+1]-H [i+1][j])
where EQU .DELTA.x=(x-x[i])/(x[i +1]-x[i]),
and EQU .DELTA.y=(y-y[j])/(y[j+1]-y[i]).
The equations are modified appropriately if the point lies in the upper triangle.
Notice that the differences between the known table values (i.e. (H[i+1][j]-H[i][j]), etc . . . ) must be calculated for the interpolation of each color which falls within the triangle defined by (i,j)-(i+1,j)-(i+1,j+1) and therefore using this difference. When performing interpolations for a large number of pixels (i.e. an scanned image) it may be advantageous to compute all the possible differences once, store them, and then use them when needed. The tradeoff in doing this is the time for computing the differences during each interpolation operation versus the cost of having to store and access the differences.
The easiest way to store and access these differences is to go to each rectangle in the plane (or rectangular solid in the three dimensional space) and compute all the differences associated with that rectangle. With reference to FIG. 2, in the two dimensional example this means that four differences for each node point in the table must be stored: EQU .DELTA.H.sub.x1 [i][j]=H[i+1][j]-H[i][j] EQU .DELTA.H.sub.x2 [i][j]=H[i+1][j+1]-H[i][j+1] EQU .DELTA.H.sub.y2 [i][j]=H[i][j+1]-H[i][j] EQU .DELTA.H.sub.y1 [i][j]=H[i+1][j+1]-H[i+1][i]
These differences correspond to the differences in the x-direction along the top and bottom of a rectangle with the H[i][j] at the lower left hand node, and the differences in the y-direction along the left and right hand sides of the triangle formed by the diagonal of this rectangle. In the three dimensional case, 12 difference values are stored. This is a significant memory overhead, and methods of reducing the overhead are desired.
The references cited herein are incorporated by reference for the teachings.